PROGRAMACIÓN
IMPERATIVA

La programación en la arquitectura von Neumann

“El ordenador ha producido un cambio de paradigma” (Gregory Chaitin)


La Arquitectura von Neumann

Concepto

El modelo von Neumann consiste básicamente en considerar a la máquina como una secuencia de celdas de memoria en la que se almacenan los datos y el propio programa. Este modelo está inspirado en la máquina de Turing universal [Turing, 1936].

En los primeros tiempos de la informática, la programación de un ordenador consistía en la construcción de una secuencia de instrucciones en código de máquina. Estas instrucciones manipulaban los datos contenidos en los registros y en las celdas de memoria, a las que se accedía mediante direcciones. Desde entonces, aunque los lenguajes han evolucionado, los “principios” de la programación siguen siendo los mismos: Este modelo de la máquina subyace incluso en los lenguajes de tercera generación, que proporcionan un acceso a la máquina de alto nivel de abstracción. Estos lenguajes tienen dos características, que se arrastran desde la concepción de los lenguajes de primera generación:
  1. Son imperativos.
  2. Están orientados a sentencias.
Desde los principios de los ordenadores, el modelo von Neumann ha tenido una influencia decisiva. Por una parte ha sido el gran motor del desarrollo informático. Por otra ha condicionado la estructura de los lenguajes de programación, ejerciendo una influencia limitadora, imponiendo una concepción restringida de la naturaleza de la computación, basada en referencias implementadoras, en la existencia de un cierto modelo de máquina.


Los lenguajes imperativos

El paradigma imperativo está orientado a sentencias o instrucciones, con estructuras de control del flujo de ejecución de un programa. Cuando el lenguaje dispone además de un mecanismo de construcción de procedimientos y funciones, se le llama también Paradigma Procedural o Procedimental. Ejemplos de lenguajes procedimentales son Pascal y C.

Los lenguajes imperativos clásicos se basan en tres ideas:
  1. Las variables.
    La memoria se compone de un conjunto de celdas. A las celdas se les pueden asignar nombres simbólicos para almacenar, actualizar y recuperar la información. Una variable es una abstracción del concepto de celda de memoria y tiene los atributos de:


  2. La asignación.
    Todo valor calculado debe almacenarse en una celda determinada. Esto se realiza mediante una sentencia de asignación, que es la abstracción de la modificación del contenido de una celda de memoria.

    Una extraña y antinatural forma de asignación que suele utilizarse es, por ejemplo:


    A la izquierda del signo "=" nos referimos a la dirección de la variable x. A la derecha nos referimos al contenido de x. Esto no es consistente, pues la consistencia consiste en mantener la semántica de manera independientemente del contexto.

    Hehner [1978] observó que el clásico operador de asignación del modelo von Neumann está pensado al revés: es decir, es más lógico decir “asignar un nombre a un objeto” que “asignar el valor (objeto) a una posición de memoria, es decir, indirectamente a un nombre.

  3. La repetición.
    Es un concepto que se aplica exclusivamente a una secuencia de sentencias para su ejecución iterativa.

Programación Estructurada

Las estructuras de control genéricas

La llamada “Programación Estructurada” [Dijkstra, 1976] permite especificar de forma clara y ordenada el control del flujo de ejecución de un programa. No contempla la sentencia “go to” [Dijkstra, 1968] por dos razones:
  1. Por tratarse de un mecanismo implementador, de bajo nivel. De hecho, los dos únicos mecanismos de control del flujo de ejecución de un procesador son secuenciación y salto.

  2. Porque dificulta la legibilidad y la comprensión de los programas.
La Programación Estructurada se basa en sólo tres estructuras de control genéricas:
  1. Secuencia.
    Es el mecanismo más simple. Se usa para indicar que las unidades de programa (sentencias o bloques de sentencias) a1 ... an se ejecutarán en secuencia, una tras otra.

  2. Selección exclusiva.
    Es la selección de sólo una unidad entre un cierto número de unidades de programa alternativas. Dadas las unidades a1 ... an, se selecciona la unidad ai (1 ≤ i ≤ n).

  3. Iteración.
    Es la repetición sucesiva (un cierto número de veces) de una unidad de programa a. El número de veces a evaluar se establece mediante una variable de control o una condición.
Mediante estas tres estructuras de control es posible expresar el flujo de ejecución de cualquier programa [Böhm, 1966].

Estas tres estructuras de control han promovido una estandarización conceptual de la especificación del control de flujo, debido a su facilidad de comprensión y de aplicación. De hecho se trata de una humanización de la especificación del control del flujo [Dijkstra, 1965], junto con una reducción de la complejidad.

Aunque existe consenso general en la utilización de estas tres estructuras, los modernos lenguajes de programación distorsionan la semántica "natural" de la Programación Estructurada, alejándose de la deseada estandarización formal. Ello es debido a la existencia de diferentes estructuras de control, incluso redundantes.

Pese al notable avance que supuso esta técnica de programación, subsisten dos importantes limitaciones:
  1. Los lenguajes de programación ofrecen solo unas estructuras de control fijas y predeterminadas. No es posible definir estructuras de control “a medida” de las necesidades.

  2. Las estructuras de control no son genéricas. Solo se pueden aplicar al código fuente. No pueden aplicarse a los datos.

Selección exclusiva

La forma más habitual y conocida de selección es mediante el mecanismo IF-THEN-ELSE, que está plenamente soportado y aceptado por todo los lenguajes imperativos: La condición (verdadera o falsa) es el resultado de la evaluación de una expresión lógica. Y se distinguen dos bloques: el bloque IF (asociado a la condición verdadera) y el bloque ELSE (asociado a la condición falsa).

El bloque ELSE es opcional. En este caso la forma es: Muchos lenguajes de programación soportan la instrucción CASE, que constituye una generalización de IF-THEN-ELSE en dos sentidos:
  1. Se admite normalmente cualquier tipo de expresión y no sólo una expresión lógica.

  2. La forma es multicamino, es decir, pueden existir más de dos alternativas.
La forma típica es: El bloque ELSE es también opcional.

Una forma más genérica sería utilizar n condiciones: en donde se supone que las condiciones son excluyentes. Si no lo son, solo se ejecuta la unidad ai correspondiente a la primera condición ci que se cumpla.

Limitaciones y problemática:
Iteración

La estructuras de control para iteración (o bucles) son tradicionalmente de dos categorías:
  1. Número de iteraciones fijo.
    La forma clásica es la siguiente:


    La variable de control v es de tipo entero y v1, v2 y v3 son expresiones enteras. STEP v3 es opcional (por defecto, supone v3=1). El bloque a se llama “cuerpo” del bucle.

  2. Número de iteraciones variable.
    El control se realiza mediante la evaluación de una condición, que se especifica al comienzo o al final del bucle. Las formas clásicas son:

    Condición
    arriba    		Condición
    abajo
    WHILE condición
        a
    END WHILE     		REPEAT
        a UNTIL condición
Limitaciones y problemática:
Implementación en MENTAL

Especificación del IF-THEN-ELSE clásico

La forma del IF-THEN-ELSE clásico se especifica mediante la forma condicional completa: En ambos casos, si la condición c se cumple, se evalúa a1. Si no se cumple, se evalúa a2. Si no existe bloque ELSE, basta con especificar (a1 ← c) o bien (c → a1). Si se cumple c, se evalúa a1. Análogamente, si sólo existe bloque ELSE (condición contraria), se especifica (a2 ←' c) o bien (c →' a2).

Ejemplos:
  1. (a ← x>3 →' b) // si x>3, tenemos a. En caso contrario, tenemos b

  2. (a ← x>3) // si x>3, tenemos a.

  3. (a ← (x>3 ∧ x<10) →' b) // Si x>3 y x<10, tenemos a. En caso contrario, tenemos b

  4. (a ← (x>3 ∨ y>5) →' b) // Si x>3 ó y>5, tenemos a. En caso contrario, tenemos b

  5. (a ← (x=1 ∨ x=2 ∨ x=3) →' b) // Si x es 1, 2 ó 3, tenemos a. En caso contrario, tenemos b

Especificación de CASE

Vamos a implementar la forma genérica siguiente: Especifica evaluar ai si se cumple la condición ci. Las condiciones c1, ... , cn pueden ser excluyentes o no.

En MENTAL se puede especificar de las formas siguientes:
  1. Secuencial (selección inclusiva).


    Se evalúan todas las ai correspondientes a las condiciones ci que se cumplan.

  2. Jerárquíca (selección exclusiva).
    Se utilizan expresiones condicionales completas anidadas.


    En este caso, se evalúan las condiciones de forma jerárquica descendente, es decir, primero se evalúa c1; si no se cumple, se evalúa c2, etc. Al final sólo se evaluaría una de las ai.

    Para mayor claridad, se pueden especificar en diferentes líneas y con desplazamientos relativos. Por ejemplo, para tres condiciones:

    (a1 ← c1 →'
        (a2 ← c2 →'
           (a3 ← c3 →' a4)
       )
    )

    La expresión condicional completa jerarquizada de tres niveles


    se puede representar mediante


    siendo


    es decir,


    En general, para n condiciones,


Bucle simple

Para determinar la estructura asociada a un bucle, el mejor método es partir de la forma extensiva (desarrollada) e ir compactándola sucesivamente identificando expresiones comunes, para obtener finalmente una expresión reducida, que luego se generaliza.

Un ejemplo simple de estructura sería la evaluación sucesiva del cuerpo a con los valores 1, 3 y 5 de la variable x: Si llamamos (v = (1 3 5)↓) , es decir, la secuencia abierta de valores que recorre la variable x, tenemos finalmente la expresión general: que podemos expresar de forma parametrizada así: siendo; El bucle simple clásico se especificaría como:

bucle(v (v1 v1+v3 … v2) a)


Bucles jerarquizados

Son bucles anidados o de orden superior en donde para cada valor de variable de un bucle de un nivel, se recorren todos los valores del resto de las variables correspondientes a los niveles inferiores. Vamos ahora a analizar las formas siguientes:

NivelesBucle
1 FOR x1 = v1
    a1
END FOR
2 FOR x2 = v2
    a2
    FOR x1 = v1
       a1
    END FOR
END FOR
3 FOR x3 = v3
    a3
    FOR x2 = v2
       a2
       FOR x1 = v1
          a1
       END FOR
    END FOR
END FOR

En donde x1, x2, x3, ... son las variables de control, y v1, v2, v3, ... son las secuencias (expresiones abiertas) de valores correspondientes a dichas variables.

El bucle de un nivel es: El bucle de dos niveles es: El bucle de tres niveles es: En general, para n niveles, tenemos un hiperbucle, es decir, una estructura de bucles anidados con el número de niveles variable: Ejemplo:
Bucles de repetición finita

Son bucles en los que el cuerpo a se evalúa un cierto número n de veces (fijo o variable). Su estructura asociada es: siendo n el número de veces a evaluar el cuerpo a. En este caso, no se necesita ninguna variable de control del bucle.


Bucles condicionales

Son los que utilizan una condición para finalizar un bucle:
  1. Bucle con la condición arriba (la condición se evalúa al principio de cada ciclo). Su forma clásica es:


    En MENTAL:


    Se puede especificar también utilizando palabras clave:


  2. Bucle con la condición abajo (la condición se evalúa al final de cada ciclo). Su forma clásica es:


    En MENTAL:


    Se puede especificar también utilizando palabras clave:


    Formas alternativas de especificar los bucles condicionales son:

    BucleCódigo
    WHILE (b = ((¡ ←' c → a) b)!
    ( (¡ ←' c → a)★ )!
    REPEAT (b = ((a ← c →' ¡)!
    ( a (c →' ¡)★ )!

Ventajas de MENTAL para la especificación de estructuras de control
Procedimientos

Un procedimiento es una unidad de programa que realiza una cierta tarea. En un procedimiento se pueden definir parámetros, que pueden ser: de entrada, de salida y de entrada/salida.

Al invocar un procedimiento, si un parámetro es de salida o de entrada/salida, hay que especificar el nombre del parámetro. Este es un aspecto análogo al de los lenguajes imperativos tradicionales, donde se distingue entre contenido (valor) y dirección de una variable. En MENTAL, el equivalente a dirección es el nombre de una variable.

Ejemplos:
  1. Clasificación ascendente de una secuencia de números por el método de la burbuja.

    Se compara el primer componente de la secuencia con cada uno del resto de los componentes, intercambiado los componentes si no están en orden ascendente. Se hace lo mismo con el segundo componente respecto al resto (del tercero en adelante). Y así sucesivamente hasta llegar al penúltimo componente, que se compara con el último. En este caso solo hay un parámetro (la secuencia), que es de entrada/salida.

    ⟨( clasif(s) = ((n = s#) // longitud de la secuencia

    [(i = [1…(n−1)]) // recorrer los elementos

    [(j = [(i+1)…n]) // recorrer siguientes

    ((s\i) > s\j) → ((u = s\i) //intercambiar

    ((s\i) = s\j) ((s\j) = u)))
    ]
    ]
    )
    )⟩

    (s = (36 5 17 12)) // secuencia ejemplo

    clasif( s ) // se utiliza el nombre como parámetro

    s // ev. (5 12 17 36) (secuencia clasificada)

  2. El mismo procedimiento anterior, pero con dos parámetros: una de entrada (s) y otro de salida (t).

    ⟨( clasif(s t) = ((n = s#) // longitud de la secuencia

    (t = s) // copiar secuencia de entrada

    [(i = [1…(n−1)]) // recorrer los elementos

    [(j = [(i+1)…n]) // recorrer siguientes

    ((t\i) > t\j) → ((u = t\i) //intercambiar

    ((t\i) = t\j)((t/j) = u)))
    ]
    ]
    )
    )⟩

    (s = (36 5 17 12)) // secuencia ejemplo

    clasif(s t)

    s // ev. (36 5 17 12)) (secuencia original)

    t // ev. (5 12 17 36) (secuencia clasificada)
Se podía haber definido también clasif(s) como función: con s como parámetro de entrada y como salida de la función la secuencia clasificada.


Bibliografía